﻿#region Header

/*
Behavioral Rating of Dancing Human Crowds based on Motion Patterns
By

Pascal Hauser 
Dipl. Ing. in Informatik, Hochschule für Technik Rapperswil, 2006
Master Thesis, Hochschule für Technik Rapperswil, 2008-2010

and

Raphael Gfeller
Dipl. Ing. in Informatik, Hochschule für Technik Rapperswil, 2006
Master Thesis, Hochschule für Technik Rapperswil, 2008-2010

*/

#endregion

#region Usings

using System.Collections.Generic;
using System.Linq;
using Sebarf.Diagnostics.Interfaces;
using Sebarf.Services.Interfaces;

#endregion

namespace paravili.Services {
	/// <summary>
	/// Does the matching by:
	/// while (a node has more than one outgoing connection or a node has more than one ingoing connection)
	///   1. foundConnectionThatIsForced=false
	///   2. eliminate connections that are forced --> foundConnectionThatIsForced=true
	///   3. if (!foundConnectionThatIsForced)
	///         eliminate the connection with the overall most cost
	/// </summary>
	public class DoMatchingByAFastSocialHeuristicService : Service, IDoMatchingService {
		#region Private Methods

		private static Match[] eleminateMultipleConnectionDeterministic(int[,] data,
																		 Dictionary<int, IList<int>> outConnection,
																		 Dictionary<int, IList<int>> inConnection) {
			var toReturn = new List<Match>();

			KeyValuePair<int, IList<int>>[] sortedOutDictionary1 =
				outConnection.OrderBy(x => x.Value.Count == 0 ? int.MinValue : -1 * x.Value.Max(c => data[x.Key, c])).ToArray();

			foreach (var outCnn in sortedOutDictionary1) {
				if (outCnn.Value.Count == 1) {
					// only one outgoing connection
					// find target
					int targetCluster = outCnn.Value[0];
					// find other cluster pointing to the targetCluster
					IList<int> target = inConnection[targetCluster];
					if (target.Count == 1) {
						int fromCluster = outCnn.Key;
						int toCluster = targetCluster;

						toReturn.Add(CreateMatch(fromCluster, toCluster, data));
						// clean structure
						RemoveConnection(fromCluster, toCluster, inConnection, outConnection, data);
					}
					else if (target.Count == 0) {
						Check.AssertException(false, "inconsistent datastructure");
					}
					else {
						// only one outgoing connection, but more incomming connection

						bool isDeterministicConnection = true;
						foreach (int entry in target) {
							if (outConnection[entry].Count > 1) {
								isDeterministicConnection = false;
								continue;
							}
						}
						if (isDeterministicConnection) {
							// find best solution
							int fromCluster =
								target.Select(x => new { Index = x, Distance = data[x, targetCluster] }).OrderBy(x => x.Distance).Last().Index;
							int toCluster = targetCluster;

							toReturn.Add(CreateMatch(fromCluster, toCluster, data));
							int[] backupData = target.ToArray();
							foreach (int cnn in backupData) {
								// clean structure
								RemoveConnection(cnn, toCluster, inConnection, outConnection, data);
							}
						}
						else {
							// has all others connection more possibilities?
							bool hasNoMorePossibilities = true;
							foreach (int entry in target) {
								if (!(outConnection[entry].Count > 1 || entry == outCnn.Key)) {
									hasNoMorePossibilities = false;
									break;
								}
							}
							if (!hasNoMorePossibilities) {
								int fromCluster = outCnn.Key;
								int toCluster = targetCluster;
								toReturn.Add(CreateMatch(fromCluster, toCluster, data));
								// clean structure
								RemoveConnection(fromCluster, toCluster, inConnection, outConnection, data);
							}
						}
					}
				}
			}

			return toReturn.ToArray();
		}

		private static Match CreateMatch(int fromCluster, int toCluster, int[,] data) {
			// match is descrete use it
			return new Match { FromIndex = fromCluster, ToIndex = toCluster, Distance = data[fromCluster, toCluster] };
		}

		private static void RemoveConnection(int fromCluster, int toCluster, Dictionary<int, IList<int>> inConnection,
											  Dictionary<int, IList<int>> allOutCnn, int[,] data) {
			Check.AssertException(allOutCnn.Sum(y => y.Value.Count) == inConnection.Sum(y => y.Value.Count), "dsfsdaff");

			foreach (var inCnn in inConnection) {
				if (inCnn.Key == fromCluster || inCnn.Key == toCluster) {
					inCnn.Value.Clear();
				}
				inCnn.Value.Remove(fromCluster);
				inCnn.Value.Remove(toCluster);
			}

			foreach (var outCnn in allOutCnn) {
				if (outCnn.Key == fromCluster || outCnn.Key == toCluster) {
					outCnn.Value.Clear();
				}
				outCnn.Value.Remove(fromCluster);
				outCnn.Value.Remove(toCluster);
			}
			for (int i = 0; i < data.GetLength(0); i++) {
				data[fromCluster, i] = int.MinValue;
				data[i, fromCluster] = int.MinValue;
				data[toCluster, i] = int.MinValue;
				data[i, toCluster] = int.MinValue;
			}
		}

		private static int[,] eliminateAtoADistances(int[,] data) {
			for (int i = 0; i < data.GetLength(0); i++) {
				data[i, i] = int.MinValue;
			}
			return data;
		}

		private static int[,] eliminateTwoFaceConnection(int[,] data) {
			for (int i = 0; i < data.GetLength(0); i++) {
				for (int y = 0; y < data.GetLength(1); y++) {
					if (data[i, y] > int.MinValue && data[y, i] > int.MinValue) {
						if (i == y) {
							continue;
						}
						if (data[i, y] > data[y, i]) {
							data[y, i] = int.MinValue;
						}
						else {
							data[i, y] = int.MinValue;
						}
					}
				}
			}
			return data;
		}

		private static Dictionary<int, IList<int>> calculateOutgoingConnection(int[,] data) {
			var toReturn = new Dictionary<int, IList<int>>();
			for (int i = 0; i < data.GetLength(0); i++) {
				var outConnections = new List<int>();
				for (int y = 0; y < data.GetLength(0); y++) {
					if (data[i, y] > int.MinValue) {
						outConnections.Add(y);
					}
				}
				toReturn.Add(i, outConnections);
			}
			return toReturn;
		}

		private static Dictionary<int, IList<int>> calculateIncomingConnection(int[,] data) {
			var toReturn = new Dictionary<int, IList<int>>();
			for (int i = 0; i < data.GetLength(0); i++) {
				var outConnections = new List<int>();
				for (int y = 0; y < data.GetLength(0); y++) {
					if (data[y, i] > int.MinValue) {
						outConnections.Add(y);
					}
				}
				toReturn.Add(i, outConnections);
			}
			return toReturn;
		}

		#endregion

		#region IDoMatchingService Members

		public Match[] FindMatch(int[,] data) {
			var toReturn = new List<Match>();

			// eliminate two way connection
			data = eliminateTwoFaceConnection(data);
			data = eliminateAtoADistances(data);

			// calculates outgoing connections
			Dictionary<int, IList<int>> outConnection = calculateOutgoingConnection(data);

			// calculates ingoint connections
			Dictionary<int, IList<int>> inConnection = calculateIncomingConnection(data);

			Check.AssertException(outConnection.Sum(y => y.Value.Count) == inConnection.Sum(y => y.Value.Count), "false sum");
			bool addMatch;
			bool cancelCondition;
			do {
				int countMatch = toReturn.Count;
				// eleminates multiple connection to one cluster on a deterministic way
				toReturn.AddRange(eleminateMultipleConnectionDeterministic(data, outConnection, inConnection));

				// eleminates multiple connection to one cluster on a deterministic way
				toReturn.AddRange(eleminateMultipleConnectionDeterministic(data, inConnection, outConnection));
				addMatch = countMatch < toReturn.Count;

				cancelCondition = ((outConnection.Any(x => x.Value.Count > 1) || inConnection.Any(x => x.Value.Count > 1)));
				if (cancelCondition && !addMatch) {
					// we have a problem
					// just remove the highest connection that can be found
					var toRemove =
						outConnection.Select(
							c =>
							new {
								c.Key,
								Target =
							c.Value.Select(x => new { Target = x, Distance = data[c.Key, x] }).OrderBy(o => o.Distance).FirstOrDefault()
							});
					var ordered = toRemove.OrderBy(c => c.Target != null ? -1 * c.Target.Distance : int.MinValue).Last();
					RemoveConnection(ordered.Key, ordered.Target.Target, inConnection, outConnection, data);
				}
			} while (cancelCondition || addMatch);

			return toReturn.ToArray();
		}

		#endregion
	}
}